The present invention relates to the recognition of geometric features in image data. Specifically, the invention relates to a generalized neighborhood concept that allows the use of correlation of local information from different portions or neighborhoods of an image in order to provide enhanced capabilities of extracting features from the image data. Quite specifically, the invention is based on the correlated use of multiple neighborhoods. The data contained in such neighborhoods are provided as an input to a parameter transform to produce a density function in the parameter space of the feature. Through a competitive process extracted features, statistically linked with portions of the image, are isolated from noise in the image. The result is a complete segmentation of the image in terms of the features as well as the parametric description of such features.
The invention is useful in computer vision for recognition of objects in image data. Some applications include printed circuit board inspection, medical images recognition, photographic or other image analysis.
Parameter transforms play a very important role in the recognition of geometric features in image data. Local operators devised to compute parametric descriptions of geometric entities using a small neighborhood w(x,y) about points of interest have been successfully employed.
In a typical feature extraction paradigm, a parameter transform is used to detect possible instances of a feature in the image data. A small neighborhood operator is devised to locally extract the parameters of the feature. The resultant local feature estimates are subsequently combined globally in order to find the geometric features. These techniques have been successfully employed, to detect, for example, lines and circles. However, detecting more complicated features has proven to be difficult.
Operators of the type described fail to exploit the long distance correlation present in the image, i.e. distant points belonging to the same geometric feature. The parameter transforms become increasingly sensitive to noise as the differential order of the geometric properties, e.g. position, direction, curvature, torsion, etc., increase. That is, to extract complex geometric features, the transforms rely on extracting higher order geometric properties using small neighborhood operators; these operations are extremely noise sensitive. Such techniques are described, for instance, in the articles "Use of the Hough Transform to Detect Lines and Curves in Pictures" by R.O. Duda and P. E. Hart, Comm. of the ACM, Vol. 15, No. 1, January 1972, pp. 11-15; in the book "Pattern Classification and Scene Analysis", by R. O. Duda and P. E. Hart, John Wiley & Sons, 1973; U.S. Pat. No. 3,069,654 entitled "Methods and Means for Recognizing Complex Patterns"; in the article by C. Kimme, D. Ballard and J. Slansky entitled "Finding Circles by an Array of Accumulators", Comm. of the ACM, Vol 18, No. 2, February 1975, pp 120-122; in the article by S. D. Shapiro entitled "Properties of the Transform for the Detection of Curves in Noisy Pictures", Comp. Graphics and Image Processing, Vol. 8, 1978, pp. 219-236; in the article by S. D. Shapiro entitled "Feature Space Transforms for Curve Detection", Pattern Recognition, Vol. 10, 1978, pp. 129-143; and in the article by J. Slansky entitled "On the Hough Transform for Curve Detection", IEEE Trans. on Comp., Vol. 27, No. 10, October 1978, pp. 923-926.
The generalized neighborhood approach, by correlating local information over different portions of the image, produces up to two orders of magnitude improvement in accuracy over conventional techniques. In the present invention, the results of the transform are filtered by the introduction of competitive processes in the parameter spaces of the type sometimes used in connectionist networks. A technique is designed for the generation of lateral inhibition links in the network, consistent with the generalized neighborhoods concept. Based on statistical coupling between features and portions of the image, features that occupy overlapping portions of the image compete so that, at the end of the process, only non-overlapping features survive, thus resulting in an implicit segmentation of the scene. Generalized neighborhood techniques are described in the article by A. Califano entitled "Feature Recognition Using Correlated Information Contained in Multiple Neighborhoods", in Proc. 7th AAAI Nat'l Conf. on Artificial Intell., St. Paul, Minn., Aug. 21-26, 1988, pp. 831-836 and in the article by A. Califano, R. M. Bolle, R. W. Taylor entitled "Generalized Neighborhoods: A New Approach to Complex Parameter Feature Extraction", IBM Tech. Report RC 14305.
The computational complexity of the technique expands linearly with the area of the image, and the method is completely parallel.